package leetcode.code1001;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：74 ms, 在所有 Java 提交中击败了69.23%的用户
//
//内存消耗：56.1 MB, 在所有 Java 提交中击败了35.38%的用户
//
//通过测试用例：45 / 45
public class Solution2 implements IDebug {

	int n, n1;

	// 包括自己，一圈全灭掉
	int[] d = new int[] { 0, 0, 1, 0, -1, 0, 0, 1, 0, -1, -1, -1, 1, -1, -1, 1, 1, 1 };

	public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
		this.n = n;
		this.n1 = n - 1;
		Map<Long, Integer> rowLight = new HashMap<>();// 行被点亮的灯个数
		Map<Long, Integer> colLight = new HashMap<>();// 列被点亮的灯个数
		Map<Long, Integer> leftLight = new HashMap<>();// 左上到右下点亮的灯个数
		Map<Long, Integer> rightLight = new HashMap<>();// 右上到左下点亮的灯个数
		Set<Long> light = new HashSet<>();
		// 点灯
		for (int[] lamp : lamps) {
			int x = lamp[0], y = lamp[1];// 检查每一个灯
			long me = this.index(x, y);// 灯标识
			if (!light.contains(me)) {// 筛选重复的灯
				light.add(me);// 记录检查过的灯，灭灯备用
				int[] represents = this.represents(x, y);
				this.lightAdd(represents[0], represents[1], rowLight);// 点亮行
				this.lightAdd(represents[2], represents[3], colLight);// 点亮列
				this.lightAdd(represents[4], represents[5], leftLight);// 左上
				this.lightAdd(represents[6], represents[7], rightLight);// 右上
			}
		}
		int len = queries.length;
		int[] ans = new int[len];// 答案
		int pans = 0;
		// 查询答案，灭灯
		for (int[] query : queries) {
			int x = query[0], y = query[1];
			int[] represents = this.represents(x, y);
			int theAns = 0;
			if (islight(represents[0], represents[1], rowLight) || islight(represents[2], represents[3], colLight)
					|| islight(represents[4], represents[5], leftLight)
					|| islight(represents[6], represents[7], rightLight)) {
				// 任何一个亮着灯，都照亮这个位置
				theAns = 1;
			}
			ans[pans++] = theAns;
			// 灭灯
			this.closeRound(x, y, rowLight, colLight, leftLight, rightLight, light);
		}
		return ans;
	}

	// 包括自己，一圈全灭掉
	private void closeRound(int x, int y, Map<Long, Integer> rowLight, Map<Long, Integer> colLight,
			Map<Long, Integer> leftLight, Map<Long, Integer> rightLight, Set<Long> light) {
		for (int i = 0; i < 18; i += 2) {
			int curx = x + d[i], cury = y + d[i + 1];
			if (curx >= 0 && curx < n && cury >= 0 && cury < n) {// 越界就不做了
				long me = this.index(curx, cury);
				if (light.contains(me)) {// 没灭的才灭灯
					this.close(curx, cury, rowLight, colLight, leftLight, rightLight, light);
					light.remove(me);
				}
			}
		}
	}

	// 判断是否亮灯
	private boolean islight(int x, int y, Map<Long, Integer> map) {
		long index = this.index(x, y);
		return map.containsKey(index);
	}

	// 灭一盏灯的四条线
	private void close(int x, int y, Map<Long, Integer> rowLight, Map<Long, Integer> colLight,
			Map<Long, Integer> leftLight, Map<Long, Integer> rightLight, Set<Long> light) {
		int[] represents = this.represents(x, y);
		this.lightSub(represents[0], represents[1], rowLight);
		this.lightSub(represents[2], represents[3], colLight);
		this.lightSub(represents[4], represents[5], leftLight);
		this.lightSub(represents[6], represents[7], rightLight);
	}

	// 灭灯，记录-1
	private void lightSub(int x, int y, Map<Long, Integer> map) {
		long index = this.index(x, y);
		int val = map.getOrDefault(index, 0);
		if (val > 1) {
			map.put(index, val - 1);
		} else if (val == 1) {
			map.remove(index);
		}
	}

	// 点灯，记录+1
	private void lightAdd(int x, int y, Map<Long, Integer> map) {
		long index = this.index(x, y);
		int val = map.getOrDefault(index, 0);
		map.put(index, val + 1);
	}

	// 二维转一维代表点
	private long index(int x, int y) {
		return (long) x * this.n + y;
	}

	// 一条线，灯照在左或者上，
	// 另一条，灯照在上或者右
	private int[] represents(int x, int y) {
		int[] ans = new int[8];
		ans[0] = x;// 行代表(x,0)
		ans[1] = 0;
		ans[2] = 0;// 列代表(0,y)
		ans[3] = y;
		if (x >= y) {
			ans[4] = x - y;
			ans[5] = 0;
		} else {
			ans[4] = 0;
			ans[5] = y - x;
		}
		// x与this.n - 1 - y比较大小换算出来如下
		int add = x + y;
		if (add >= this.n1) {
			ans[6] = add - this.n1;
			ans[7] = this.n1;
		} else {
			ans[6] = 0;
			ans[7] = add;
		}
		return ans;
	}

	@Override
	public void debug1() {
		int[] e = HelpDebug.str2array3("[1,0]");
		HelpDebug.compare(e, this.gridIllumination(5, HelpDebug.str2array1("[[0,0],[4,4]]"), HelpDebug.str2array1("[[1,1],[1,0]]")));
	}

	@Override
	public void debug2() {
		int[] e = HelpDebug.str2array3("[1,1]");
		HelpDebug.compare(e, this.gridIllumination(5, HelpDebug.str2array1("[[0,0],[4,4]]"), HelpDebug.str2array1("[[1,1],[1,1]]")));
	}

	@Override
	public void debug3() {
		int[] e = HelpDebug.str2array3("[1,1,0]");
		HelpDebug.compare(e, this.gridIllumination(5, HelpDebug.str2array1("[[0,0],[0,4]]"), HelpDebug.str2array1("[[0,4],[0,1],[1,4]]")));
	}

	@Override
	public void debug4() {
		int[] e = HelpDebug.str2array3("[1,0]");
		HelpDebug.compare(e, this.gridIllumination(2, HelpDebug.str2array1("[[0,1]]"), HelpDebug.str2array1("[[1,0],[1,1]]")));
	}

	public static void main(String[] args) {
//		2
//		[[0,1]]
//		[[1,0],[1,1]]
		Solution2 so = new Solution2();
		so.debug4();
		so.debug1();
		so.debug2();
		so.debug3();
	}

}
